1. Field of the Invention
This invention relates to data processing systems, and in particular to a data processing system using controllable interleaving of information stored in different attached memory units.
2. Description of the Prior Art
Interleaving of information stored in different memories in a data processing system is known. In data processing systems with more than one memory the speed of the overall system operation may be increased by placing sequential memory addresses in different memory units. In this manner the total time taken to access a sequence of memory locations may be reduced because several memory accesses may be overlapped by a central processing unit operating at a speed greater than the speed of the individual memories. FIGS. 10a to 10c (from Encyclopedia of Computer Science, A. Ralston, editor, Petrocelli Charter 1976) provide an example. In FIG. 10, it is assumed that 0.6 microseconds are required to take a word from memory to the central processing unit, that 1.2 microseconds are required after the initiation of an access to a given memory before the memory unit may again be accessed, that the central processing unit requires 0.2 microseconds to prepare a memory request and 0.2 microseconds to handle the response in the desired manner.
As illustrated in FIG. 10a, without interleaving a sequence of four memory accesses would require 4.6 microseconds. The CPU first prepares request A which consumes 0.2 microseconds, then memory M is accessed for information A and the CPU handles the results, for a total of 1 microsecond. Request B may then be prepared, but it cannot be supplied to memory M until 1.2 microseconds have elapsed, at which time memory M may be reaccessed. In a similar manner, requests C and D are prepared and responses received.
FIG. 10b shows that the effect of two-way interleaving is to substantially reduce the overall time for four memory accesses and responses. As shown in FIG. 10b, requests A and B are prepared by the CPU, but because requests A and C are made to one memory while requests B and D to another memory, the total time is shortened to 2.4 microseconds.
FIG. 10c illustrates the effect of four-way interleaving to further reduce total access response time. As shown in FIG. 10c, the four requests A through D are prepared, supplied to separate memories, then returned to the CPU in a total of 1.6 microseconds. FIG. 10c also illustrates that the central processing unit is fully occupied given the assumed operating speeds above. Thus for the system depicted, further interleaving beyond four ways will not increase the overall system speed because the overall system speed is now CPU limited rather than memory limited.
Interleaving and its effect on overall system speed has been the subject of many technical articles. See, for example, Introduction to Computer Architecture by H. S. Stone, Science Research Associates, Inc., pages 201 et seq.; and Design of a Computer, The Control Data 6600 by J. E. Thornton, Scott, Foresman & Co., pages 44 et seq.
The typical prior art technique for accomplishing interleaving relies upon the use of switches or hardware translators. In a prior art system, the last N bits of the address of a given word provide interleaving among 2.sup.N modules. Such systems are typically lacking in flexibility because fixed determinations must be made during implementation of the system as to what information will be interleaved and the module in which it will be placed. Such systems use switches or other preset devices to control the interleaving and require memories which are all the same size and have the same addresses. If one or more memory modules is made larger or smaller than other memory modules, the switches controlling the interleaving must be manually reset.